Exponentiation is a fundamental operation in many cryptographic applications, including multi-party public key encryption, decryption and digital signature protocols. Exponentiation is also an expensive operation in terms of the computational resources that it requires. For example, using standard window-based methods, about 200 modular multiplications are typically required per exponentiation for exponent sizes of around 160 bits. There are a number of known techniques that attempt to improve the computational efficiency of exponentiation. However, such techniques have generally only been successful in providing an improvement for so-called large batches of computations, which typically include many thousands of similar computations. More specifically, amortization techniques such as those described in J. Bos and M. Caster, “Addition Chain Heuristics,” Proceedings of CRYPTO '89, pp. 400-407, which is incorporated by reference herein, are particularly efficient for performing exponentiation in large batches.
Unfortunately, these and other techniques have been unable to provide significant improvements over the above-noted window-based methods for small batches of computations. These small batches of computations are typically associated with cryptographic applications involving smart cards and other devices having limited computational and memory resources.
It is also known in the art to utilize distributed servers to assist in performing cryptography-related computations. Examples of such techniques are described in M. Abadi, J. Feigenbaum and J. Kilian, “On Hiding Information From an Oracle,” Journal of Computer and System Sciences, Vol. 39, No. 1, pp. 21-50, August 1989, and M. Ballare, J. A. Garay and T. Rabin, “Fast Batch Verification for Modular Exponentiation and Digital Signatures,” Proceedings of EUROCRYPT '98, pp. 236-250, both of which are incorporated by reference herein.
Other known techniques are described in V. Boyko, M. Peinado and R. Venkatesan, “Speeding up Discrete Log and Factoring Based Schemes via Precomputations,” Proceedings of EUROCRYPT '98, pp. 221-235, which is incorporated by reference herein.
The above-noted conventional techniques exhibit significant drawbacks. For example, those described in the above-cited V. Boyko et al. reference generally require that the input exponents for which computation is to be performed exhibit a particular near-random distribution. These techniques are therefore not appropriate for computations involving arbitrary input values.
It is apparent from the foregoing that a need exists in the art for techniques for performing exponentiation and other computational tasks utilizing arbitrary input values and in a manner that can provide improvements over conventional techniques for both small batches and large batches of computations.